/*
 * @lc app=leetcode.cn id=23 lang=swift
 *
 * [23] 合并 K 个升序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        var nodes: [ListNode] = lists.compactMap { $0 }
        let dummy = ListNode(-1)
        var p: ListNode? = dummy
        while !nodes.isEmpty {
            nodes.sort(by: { $0.val < $1.val })
            let node = nodes.removeFirst()
            p?.next = node
            p = p?.next
            if node.next != nil {
                nodes.append(node.next!)
            }
        }
        return dummy.next
    }
}
// @lc code=end

